1. Field of the Invention
The invention relates to the allocation of bandwidth in an ATM (Asynchronous Transfer Mode) network. More particularly, the invention relates to methods and apparatus for controlling traffic and congestion via queuing structures.
2. State of the Art
A properly constructed ATM network must manage traffic fairly and provide effective allocation of the network capacity for different types of traffic such as voice, video, and data. The ATM network must also provide cost effective operations relative to the quality of service (QOS) level specified by each network user and must be able to support different delay requirements for different applications. Most importantly, the network must be able to adapt to unforseen traffic patterns, in particular unforseen bursts of traffic from various network users, i.e. network congestion.
The only way to manage network congestion, short of increasing the bandwidth of the network, is to manage the network traffic. According to various ATM standards, traffic management is largely based on QOS levels negotiated between the network operator and the network users. In general, QOS levels specify the maximum amount of traffic which each user may submit to the network in a measured period of time, i.e. a bit rate. A digital voice connection requires no more than about 32 kbits/s whereas a high definition television signal may require more than 6 Mbit/s. These predicted requirements in bandwidth are sometimes referred to as the "natural bit rate" for an application. The natural bit rate required by non-specific data transmissions may vary widely over time from as low as a few kbits/s to as high as several hundred kbits/s. This type of variable natural bit rate is said to be "bursty". The challenge to the ATM network is to support the natural bit rate of all the applications being serviced. Due to statistical bursts, it is inefficient to simply allocate bandwidth for the maximum bit rate required by the application. Because of variable traffic profiles, it may be necessary to discard traffic from certain users when the network experiences congestion.
As suggested above, congestion refers to a condition that exists at the ATM layer in the network elements such as switches, transmission links, or cross-connects where the network is not able to meet a stated and negotiated performance objective (the QOS levels specified by the network users). Traffic control, on the other hand, refers to a set of actions which are taken by the network to avoid congestion. Thus, "congestion control" is the result of QOS planning and "traffic control".
The actions which may be taken by the network to control traffic are limited by the QOS levels negotiated with the network users. In the ATM network, traffic control includes five types of actions: (1) Connection Admission Control (CAC) to determine at the time of call setup whether a user connection will be accepted or rejected; (2) Usage Parameter Control (UPC) to monitor and regulate traffic at the User Network Interface (UNI); (3) Cell Loss Priority (CLP) control to establish priorities for different types of traffic; (4) traffic shaping mechanisms to alter the nature of traffic at the UNI based on the three previously stated controls; and (5) traffic discarded based on specified policies using information from actions (1) through (4) above.
A core mechanism utilized in the ATM network is the establishment of queues at the inlet to an ATM node. Prior art FIG. 1 illustrates the simple concept of queues for different types of traffic entering a multiplexer 10 having an outlet 12 with a maximum bandwidth of, e.g., 155 mbits/s. The multiplexer has a number of inlets shown as 14, 16, 18, 20, 22, . . . , n, and each is provided with a corresponding queue (FIFO buffer) 14', 16', 18', 20', 22', . . , n'. Regardless of the bandwidth of the network, the aggregate bit rate of all of the inlets n must not exceed the bandwidth of the outlet 12 for more than a short period of time (e.g. a few milliseconds) during which the queues may prevent data loss. According to the ATM standard, each inlet queue must be serviced in a fair and equitable manner. Queue servicing operations should result in appropriate delays and acceptable data loss for each application. For example, if the queue for inlet 14 in FIG. 1 receives a constant bit rate (CBR) video signal (50-100 kbits/s), it must be serviced every 1-2 milliseconds in order to prevent data loss. On the other hand, if inlet 18 services variable bit rate voice, it may tolerate a data loss of between 1-10% of the samples and the queue for this inlet may be serviced less frequently. The highest priority queue may be the one servicing the signalling channel which contains information for managing the network, including traffic shaping controls to prevent congestion. Other data channels may receive different priority handling depending on the agreed QOS for these channels. The lowest priority queues are those carrying data which is not sensitive to delay, e.g. email.
Those skilled in the art will appreciate that the number of queues and the type of traffic being handled at any node such as the multiplexer 10 in FIG. 1 changes over time and that the node must constantly monitor the state of queues, opening new queues, closing old queues, and assuring that all queues are timely serviced. According to general principles, after the signalling channel is serviced, delay-sensitive queues are serviced for T.sub.1 ms or until the delay-sensitive queues are empty if before T.sub.1 ms. Next, the delay-insensitive queues are serviced for T.sub.2 ms or until they are empty if before T.sub.2 ms. If during the servicing times T.sub.1 and T.sub.2, the signalling channel queue needs to be serviced, the servicing of the queues is suspended and resumed when servicing of the signalling channel queue is completed.
There are three well known equations used to compute the parameters for servicing queues. The first equation, listed as Equation 1 below, assures that for each q.sub.i, a fraction f.sub.i of the output link bandwidth is available where T.sub.i is the time parameter for servicing queue q.sub.i. ##EQU1##
The second equation, listed below as Equation 2, assures that all of the bandwidth assigned to all of the queues does not exceed a fraction of (1-f.sub.0) for the output link capacity. ##EQU2##
The third equation, listed below as Equation 3, shows that the cycle time for all queues should be from 1-2 milliseconds in order to guarantee consistent service to delay sensitive traffic. ##EQU3##
In Equation 3, M.sub.c is the number of cells withdrawn from the queue during the service cycle time and t is the cell transmission time on the link.
Those skilled in the art will appreciate that one of the most difficult aspects of traffic management are related to variable delays in traffic. Traffic management operations must occur at the source UNI and at the destination UNI in order to account for traffic delays. In other words, data flowing from the network to the UNI must be buffered and data flowing from the users to the network must be buffered. Further, at each device through which data passes from a source to a destination, data must be buffered at the inlet and the outlet of the device. The nature of the traffic will determine how it is buffered and whether or not data is discarded in order to avoid congestion.
Prior art FIG. 2 illustrates the inlet and outlet buffers in a state of the art ATM device at a UNI. As shown in FIG. 2, a plurality of xDSL line inlets 30 enter a user side inlet multiplexer 32 via a plurality of user inlet queues 34 in a manner similar to that discussed above with reference to FIG. 1. The multiplexer 32 services the queues 34 according to priority as described above and places data on a local bus or switch fabric 36 from which the data enters a network side outlet multiplexer 38 via a plurality of network outlet queues 40. The multiplexer 38 services the queues 40 according to priority and delivers data to the network 42. Data from the network 42 enters a network side inlet multiplexer 44 via a plurality of network inlet queues 46. The multiplexer 44 services the queues 46 according to priority and delivers data to the internal bus or switch fabric 36 from where the data enters a user side outlet multiplexer 48 via a plurality of user outlet queues 50. The multiplexer 48 services the queues 50 and delivers data to a plurality of xDSL line outlets 52.
As mentioned above, queues are generally serviced according to timing parameters and delayed data may need to be discarded. For example, data entering one of the queues 46 from the network 42 may be discarded if buffering would serve no purpose. Thus, if one segment of a data packet is discarded, the remainder of the data packet should be discarded since it must be retransmitted anyway due to end to end flow control.
Ironically, one of the most difficult aspects of implementing traffic control is the fair allocation of available bandwidth during times of light traffic where extra bandwidth is available for distribution among users who have contracted for services such as ABR (available bit rate), UBR (unspecified bit rate), and GFR (guaranteed frame rate). In these services, users pay for a minimum cell rate or minimum frame rate which is an average rate taken over time during which there may be bursty periods and periods of latency. During bursty periods data may be discarded if traffic on the network is heavy. If traffic on the network is light, the extra available bandwidth must be apportioned to these users in a fair way. Presently, there are several different ways to apportion extra bandwidth. One way is referred to as "proportional fairness". According to proportional fairness, each user is assigned a portion of the extra bandwidth in proportion to the minimum rate for which the user contracted. Another way to apportion extra bandwidth is known as "equal fairness". According to equal fairness, each user is apportioned an equal share of the available extra bandwidth regardless of the minimum rate for which the user contracted. A third way to apportion extra bandwidth is known as "weighted fairness". According to weighted fairness, each user is apportioned a weighted share of available extra bandwidth based on one or more factors other than the minimum rate for which the user contracted.
Current implementations of proportional and equal fairness algorithms rely on statistical databases and tend to be inaccurate.